﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Security.Cryptography;
using System.Text;
using System.Threading.Tasks;

namespace Redis读写分离.Filter
{
    public class BloomFilter
    {
        private readonly BitArray _bitArray;
        private readonly int _bitArraySize;
        private readonly int _numberOfHashes;
        private readonly HashAlgorithm[] _hashAlgorithms;

        /// <summary>
        /// 初始化布隆过滤器
        /// </summary>
        /// <param name="expectedItems">预期要存储的元素数量</param>
        /// <param name="errorRate">期望的误判率(0-1)</param>
        public BloomFilter(int expectedItems, double errorRate)
        {
            if (expectedItems <= 0) throw new ArgumentException("期待值必须为正数");
            if (errorRate <= 0 || errorRate >= 1) throw new ArgumentException("错误率必须在 0 到 1 之间");

            // 计算最优的位数组大小和哈希函数数量
            _bitArraySize = (int)Math.Ceiling(-expectedItems * Math.Log(errorRate) / Math.Pow(Math.Log(2), 2));
            _numberOfHashes = (int)Math.Ceiling(Math.Log(2) * _bitArraySize / expectedItems);

            _bitArray = new BitArray(_bitArraySize);
            _hashAlgorithms = new HashAlgorithm[_numberOfHashes];

            // 使用不同种子的哈希算法来模拟多个哈希函数
            for (int i = 0; i < _numberOfHashes; i++)
            {
                _hashAlgorithms[i] = SHA256.Create();
            }
        }

        /// <summary>
        /// 添加元素到布隆过滤器
        /// </summary>
        public void Add(string item)
        {
            if (string.IsNullOrEmpty(item)) return;

            foreach (var hash in GetHashes(item))
            {
                _bitArray.Set(hash % _bitArraySize, true);
            }
        }

        /// <summary>
        /// 检查元素是否可能存在于布隆过滤器中
        /// </summary>
        /// <returns>false表示肯定不存在，true表示可能存在</returns>
        public bool Contains(string item)
        {
            if (string.IsNullOrEmpty(item)) return false;

            foreach (var hash in GetHashes(item))
            {
                if (!_bitArray.Get(hash % _bitArraySize))
                {
                    return false;
                }
            }
            return true;
        }

        /// <summary>
        /// 获取元素的多个哈希值
        /// </summary>
        private int[] GetHashes(string item)
        {
            byte[] inputBytes = Encoding.UTF8.GetBytes(item);
            int[] hashes = new int[_numberOfHashes];

            for (int i = 0; i < _numberOfHashes; i++)
            {
                // 使用不同的前缀来模拟不同的哈希函数
                byte[] prefix = BitConverter.GetBytes(i);
                byte[] combined = new byte[prefix.Length + inputBytes.Length];
                Buffer.BlockCopy(prefix, 0, combined, 0, prefix.Length);
                Buffer.BlockCopy(inputBytes, 0, combined, prefix.Length, inputBytes.Length);

                byte[] hashBytes = _hashAlgorithms[i].ComputeHash(combined);
                hashes[i] = Math.Abs(BitConverter.ToInt32(hashBytes, 0));
            }

            return hashes;
        }

        /// <summary>
        /// 计算当前布隆过滤器的近似误判率
        /// </summary>
        public double EstimatedFalsePositiveRate()
        {
            int setBits = 0;
            for (int i = 0; i < _bitArraySize; i++)
            {
                if (_bitArray.Get(i)) 
                    setBits++;
            }

            // ratio表示任意一个bit被设置为1的概率
            // 对于未插入的元素，其所有k个哈希位置都恰好被设置为1的概率就是ratio^k
            double ratio = (double)setBits / _bitArraySize;
            return Math.Pow(ratio, _numberOfHashes);
        }

        /// <summary>
        /// 清空布隆过滤器
        /// </summary>
        public void Clear()
        {
            _bitArray.SetAll(false);
        }
    }
}
